﻿// Given n denominations of coins of values V0 < V1 < ... < Vn-1 (all integers).
// Assume V0 = 1, so it can always make change for any amount of money C.
//
// Find an algorithm which makes change for an amount of money C with as few coins as possible.
//
// Algorithm: (Dynamic Programming)
// Let M(i) denote the minimum number of coins required to make change for amount of money i
// Then, M(i)=min{M(i-v[j])}+1, i>0, 0<=j<n
//       M(0)=0
//       M(i)=MAX_INT, i<0
//
// Complexity:
//   Time: O(n*C)
//   Space: O(C)

#include "stdafx.h"
#include <iostream>
using namespace std;

int g_counter=0; // global counter to calc complexity
#define MAX_INT ~((unsigned int) 0)/2

// Implement (DP):
// Using an auxiliary array Store[i] (initialized to -1) to save the minimum # of coins to make change for amount of money i, 0<=i<=c
// If can't make change for money j, let Store[j]=MAX_INT
//
// c: amount of money
// store[c+1]: auxiliary array to save the value of MakeChange(i), 0<=i<=c
int MakeChange(int *v, int n, int c, int *store)
{
	if(!v||n<=0||!store) throw;
	if(!c) return 0;

	int min=MAX_INT;
	for(int i=0;i<n;i++)
	{
		++g_counter; // global counter for complexity compute

		if(c<v[i]) continue; // if v[i]<v[i+1], break the for-loop

		if(store[c-v[i]]==-1)
			store[c-v[i]]=MakeChange(v,n,c-v[i],store);

		if(min>store[c-v[i]])
			min=store[c-v[i]];
	}

	return (min==MAX_INT ? MAX_INT : min+1); // return MAX_INT if can't make change
}
//Time: O(n*C)
//Space: O(C)



// Further thoughts I:
// Same question as above. Print out all coins as the fewest coins are selected.
//
// Implement (DP):
// Using an auxiliary array Store[i] (initialized to -1) to save the minimum # of coins to make change for amount of money i, 0<=i<=c
// If can't make change for money j, let Store[j]=MAX_INT
// Using an auxiliary array Selected[j] (initialized to -1) to save the last selected coin (face value) for amount of money i, 0<=i<n, 0<=j<=c
//
// c: amount of money
// store[c+1]: auxiliary array to save the value of MakeChange(i), 0<=i<=c
// selected[c+1]: auxiliary array to save the last selected coin (face value) for amount of money i, 0<=i<=c
int MakeChange_Print(int *v, int n, int c, int *store, int *selected)
{
	if(!v||n<=0) throw;
	if(!c) return 0;

	int min=MAX_INT;
	int index=-1;

	for(int i=0;i<n;i++)
	{
		++g_counter; // global counter for complexity compute

		if(c<v[i]) continue; // if v[i]<v[i+1], break the for-loop

		if(store[c-v[i]]==-1)
			store[c-v[i]]=MakeChange_Print(v,n,c-v[i],store,selected);

		if(min>store[c-v[i]])
		{
			min=store[c-v[i]];
			index=i;
		}
	}

	if(index!=-1)
		selected[c]=v[index];

	return (min==MAX_INT ? MAX_INT : min+1); // return MAX_INT if can't make change
}

// c: amount of money to make change
void PrintSelection(int c, int *selected)
{
	if(c<0||!selected) throw;

	for(int i=c;i>0;)
	{
		cout<<selected[i];
		i-=selected[i];
		cout<<(i>0 ? ", ":"");
	}
}


// Further thoughts II:
// Same question as above. Output the total # of possible selections (excluding duplicates).
//
// Algorithm
// Let M(i) denote the # of possible selections for money i, by using coins v[j]..v[n-1], 0<=j<n
// Therefore,
//   M(i)=Σ{M(i-v[j])}, 0<i, 0<=j<n
//   M(0)=0, i<=0
//
// Note: there's no overlap between M(i) and M(j) because we eliminate (at least) one type of coin to calc M(i) and M(j)
//
// For example,
//
//                                      c=12, coins:{6,2,10}
//       ---------------------------------------------------------------------------
//       |                              |                                          |
//       6 {6,2,10}                     10 {2,10}                                  2 {10}
// ---------------------------          -------------------------------------      -
// |     |                   |	        |	                                |      |
// 0     4 {2,10}           -4 {10}     8 {2,10}                            0     -8 {10}
//       --------------	                ------------------------------
//	     |            |	                |                            |
//       2 {2,10}    -6 {10}            6 {2,10}                    -2 {10}
//	     ------	                        ---------------------
//       |	  |                         |                   |
//       0   -8 {10}                    4 {2,10}           -4 {10}
//                                      -------------
//                                      |           |
//                                      2 {2,10}   -6 {10}
//                                      ------
//                                      |    |
//                                      0   -8 {10}
//
// c: amount of money
// index: Mark available coins {v[index]..v[n-1]}
// total: # of possible selections by using available coins
void MakeChange(int *v, int n, int c, int index, int &total)
{
	if(!v||n<=0) throw;
	if(!c)
	{
		++total; // finish a selection
		return;
	}

	for(int i=index; i<n; i++)
	{
		++g_counter; // global counter for complexity compute

		if(c<v[i]) continue;
		MakeChange(v,n,c-v[i], i ,total);
	}
}


// Optimized version
//
// Amount of Money: 12
// Coins: {10,6,3}
//
//   12 (No 10) + 12 (One 10)
// = 12 (No 10) +  2 (No 10)
//
//   12 (No 10)
// = 12 (No 10, No 6) + 12 (No 10, One 6) + 12 (No 10, Two 6)
// = 12 (No 10, No 6) +  6 (No 10, No 6)  + 1
// = 12 (Use 3) + 6 (Use 3) + 1
// = 1 + 1 + 1
// = 3
//
//   2 (No 10)
// = 2 (No 10, No 6)
// = 2 (Use 3)
// = 0
//
// Therefore, 12 (No 10) + 12 (One 10) = 3 + 0 = 3
//
//
// c: amount of money
// index: the coin currently being selected
int MakeChange_Optimized(int *v, int n, int c, int index)
{
	++g_counter; // global counter for complexity compute

	if(!v||n<=0) return 0;

	if(index==n-1) return (c%v[index]==0 ? 1 : 0);

	int total=0;
	for(int i=0; i*v[index]<=c; i++)
		total+=MakeChange_Optimized(v, n, c-i*v[index], index + 1);

	return total;
}


// Further thoughts III:
// Same question as above. Output all possible selections (excluding duplicates).
//
// Algorithm
// Let M(i) denote the # of possible selections for money i, by using coins v[j]..v[n-1], 0<=j<n
// Therefore,
//   M(i)=Σ{M(i-v[j])}, 0<i, 0<=j<n
//   M(0)=0, i<=0
//
// Note: there's no overlap between M(i) and M(j) because we eliminate (at least) one type of coin to calc M(i) and M(j)
//
//
// c: amount of money
// index: Mark available coins {v[index]..v[n-1]}
// selected[c+1]: auxiliary array (initialized to -1) to save the last selected coin (face value) for amount of money i, 0<=i<=c
// money: original amount of money to make change
void MakeChange_PrintAll(int *v, int n, int c, int index, int *selected, int money)
{
	if(!v||n<=0) throw;
	if(!c)
	{
		cout<<endl<<" ";
		PrintSelection(money,selected);
		return;
	}

	for(int i=index; i<n; i++)
	{
		++g_counter; // global counter for complexity compute

		if(c<v[i]) continue;
		selected[c]=v[i];
		MakeChange_PrintAll(v,n,c-v[i], i ,selected,money);
	}
}


int _tmain(int argc, _TCHAR* argv[])
{
	int c=12; // amount of money
	int v[]={6,2,10}; // coins
	int n=sizeof(v)/sizeof(v[0]);


	// Print out the minimum number of coins
	g_counter=0;
	int *store=new int[c+1];

	for(int i=0;i<c+1;i++) store[i]=-1;
	cout<<"Making change for amount of money: "<<c<<endl;
	for(int i=0;i<n;i++)
		cout<<(!i?"Coins: {":"")<<v[i]<<(i<n-1?", ":"}");
	cout<<endl;

	store[c]=MakeChange(v,n,c,store);
	if(store[c]==MAX_INT)
		cout<<endl<<endl<<"Minimum # of coins: no solution.";
	else
		cout<<endl<<endl<<"Minimum # of coins: "<<store[c];
	cout<<endl<<"Complexity: "<<g_counter<<endl;

	//if(c>0)
	//{
	//	cout<<"Store array: ";
	//	for(int i=0;i<c+1;i++) cout<<store[i]<<(i<c?", ":"");
	//	cout<<endl;
	//}


	// Print out all coins as the fewest coins are selected
	g_counter=0;
	for(int i=0;i<c+1;i++) store[i]=-1;
	int *selected=new int[c+1];
	for(int i=0;i<c+1;i++) selected[i]=-1;

	store[c]=MakeChange_Print(v,n,c,store,selected);
	if(store[c]==MAX_INT || !c)
		cout<<endl<<endl<<"Fewest coin selection: no solution.";
	else
	{
		cout<<endl<<endl<<"Fewest coin selection: ";
		PrintSelection(c,selected);
	}
	cout<<endl<<"Complexity: "<<g_counter<<endl;

	//if(c>0)
	//{
	//	cout<<"Store array: ";
	//	for(int i=0;i<c+1;i++) cout<<store[i]<<(i<c?", ":"");
	//	cout<<endl<<"Selected array: ";
	//	for(int i=0;i<c+1;i++) cout<<selected[i]<<(i<c?", ":"");
	//	cout<<endl;
	//}


	// Print out the total number of possible selections (excluding duplicates)
	g_counter=0;
	int index=0, total=0;

	MakeChange(v,n,c,index,total);
	cout<<endl<<endl<<"# of possible selections: "<<total;
	cout<<endl<<"Complexity: "<<g_counter<<endl;


	// Optimized version - print out the total number of possible selections (excluding duplicates)
	g_counter=0;
	index=0;
	cout<<endl<<endl<<"[*** Optimized version ***]";
	cout<<endl<<"# of possible selections: "<<MakeChange_Optimized(v,n,c,index);
	cout<<endl<<"Complexity: "<<g_counter<<endl;


	// Print out all possible selections (excluding duplicates)
	g_counter=0;
	index=0;
	for(int i=0;i<c+1;i++) selected[i]=-1;
	cout<<endl<<endl<<"All possible selections: "<<(c>0?"":"no solutions.");

	MakeChange_PrintAll(v,n,c,index,selected,c);
	cout<<endl<<"Complexity: "<<g_counter<<endl;

	delete[] store, delete[] selected;
	return getchar();
}